
#include<conio.h>
#include<malloc.h>
#include<iostream>

using namespace std;
#define order 4											
typedef struct nodestruct
{
	int key[order];										
	struct nodestruct *index_ptr[order+1];				
	int fill_fact;	
	struct nodestruct *parent;							
	
}bnode ;												

class  btree
{
	bnode *root;																		
public:
	void init(bnode* new_node);	
	void initr();							 
	void display();	
	bnode* show(bnode *t);
	void showchild(bnode* t);
	//INSERT
		int insert(int key);
		bnode* sortarray(bnode* cur,int key);	
		bnode* search_leaf(bnode* t,int key);
		void sortedentry(bnode* cur,int key);
		void sortarray1(bnode* cur,int key,int *arr);
		bnode* par_nul(bnode* t1,bnode* t2,bnode* c,int mid_val);
		bnode* par_space(bnode* t1,bnode* t2,bnode* c,int mid_val);
		bnode* par_full(bnode* t1,bnode* t2,bnode* c,int mid_val);
	//DELETE
	bnode* search_node(bnode* t,int key);
	int delete_key(int key);
	void rytdistribute(bnode* target,bnode* sibling,int pos);
    void lftdistribute(bnode* target,bnode* sibling,int pos);
    void rytmerge(bnode* target,bnode* sibling,int pos);
    void lftmerge(bnode* target,bnode* sibling,int pos);


	
};
/*INSERT SE RELATED FUNCTION*/
void btree::init(bnode *new_node)
{
	
	new_node->fill_fact = 0;
	new_node->parent = NULL;
	int i;
	for(i=0;i<=order;i++)
		new_node->index_ptr[i] =NULL;
	for(i=0;i<order;i++)
		new_node->key[i] =-1;
	
}
void btree::initr()
{
	root =(bnode*)malloc(sizeof(bnode));
	root->fill_fact = 0;
	root->parent = NULL;
	int i;
	for(i=0;i<=order;i++)
		root->index_ptr[i] =NULL;
	for(i=0;i<order;i++)
		root->key[i] =-1;
}
bnode* btree::search_leaf(bnode* current_node,int key)
{
	int i;
	if(current_node->index_ptr[0] == NULL)
	{
		
		return current_node;
	
	}
	else
	{
		bnode *c= NULL;
		if(current_node->fill_fact == 1)
		{
			if(key<current_node->key[0])
			{
				current_node = current_node->index_ptr[0];
				c = search_leaf(current_node,key);
				return c;
			}
			else
			{
				current_node = current_node->index_ptr[1];
				c = search_leaf(current_node,key);
				return c;
			}
		}
		else
		{
			for(i=0;i<(current_node->fill_fact-1);i++)
			{
				if(key<current_node->key[i])
				{
					current_node = current_node->index_ptr[i];
					c=search_leaf(current_node,key);
					return c;
				}
				else
				{
					if(key>current_node->key[i] && key<current_node->key[i+1])
					{
						current_node = current_node->index_ptr[i+1];
						c=search_leaf(current_node,key);
						return c;
					}
				}
			}
			if(key<current_node->key[i])
			{
				current_node = current_node->index_ptr[i];
				c=search_leaf(current_node,key);
				return c;
			}
			else
			{
				current_node = current_node->index_ptr[i+1];
				c=search_leaf(current_node,key);
				return c;
			}
		}
	}
}


void btree::sortedentry(bnode* cur,int key)
{
	int temp_key1 = key;
	int temp_key2= key;
	int i;
	for(i=0;i<cur->fill_fact;i++)
		{
			if(temp_key1 < (cur->key[i]))
				{
					temp_key2 = temp_key1;
					temp_key1 = cur->key[i];
					cur->key[i] = temp_key2;
				}
		}
	cur->key[i] = temp_key1;
	cur->fill_fact ++ ;
		
}
void btree::sortarray1(bnode* cur,int key, int *arr)
{
	int temp_key1,temp_key2,i;
	temp_key1=temp_key2=key;
	for(i=0;i<order;i++)
	{
		if(temp_key1 < (cur->key[i]))
		{
			temp_key2 = temp_key1;
			temp_key1 = cur->key[i];
			*(arr+i) = temp_key2;
		}
		else
		{
			*(arr+i) = cur->key[i];
		}
	}
	*(arr+i) = temp_key1;
}
bnode* btree::par_nul(bnode* t1,bnode* t2,bnode* c,int mid_val)
{
	c->index_ptr[0] = t1;
	c->index_ptr[1] = t2;
	c->key[0]= mid_val;
	int i;
	for(i=1;i<order;i++)
	{
			c->key[i] = -1;
	}
	c->fill_fact=1;
	t1->parent = c;
	t2->parent = c;
	return c;

}
bnode* btree::par_space(bnode* t1,bnode* t2,bnode* c,int mid_val)
{

	int i,f,pos;
	bnode* p;
	p = c->parent;
	f = p->fill_fact;
	for(i=0;i<=f;i++)
	{
			if(p->index_ptr[i] == c)
			{
				break;
			}
	}
	pos = i;
	if(pos == 0)
	{
			for(i=f;i>0;i--)
			{
				p->key[i] = p->key[i-1];
			}
			p->key[0] = mid_val;
			for(i=f+1;i>1;i--)
			{
				p->index_ptr[i] = p->index_ptr[i-1];
			}
			p->index_ptr[0] = t1;
			p->index_ptr[1] = t2;
			t1->parent =p;
			t2->parent = p;
			p->fill_fact++;
			return p;
	}
	else if(pos == (order-1))
	{
			p->key[order-1] = mid_val;
			p->index_ptr[order-1] = t1;
			p->index_ptr[order] = t2;
			t1->parent = p;
			t2->parent = p;
			p->fill_fact++;
			return p;
	}
	else
	{
		for(i=f;i>pos;i--)
			{
				p->key[i] = p->key[i-1];
			}
			p->key[pos] = mid_val;
			for(i=f+1;i>pos+1;i--)
			{
				p->index_ptr[i] = p->index_ptr[i-1];
			}
			p->index_ptr[pos] = t1;
			p->index_ptr[pos+1] = t2;
			t1->parent = p;
			t2->parent = p;
			p->fill_fact ++;
		
			return p;

	}
}
bnode* btree::par_full(bnode* t1,bnode* t2,bnode* c,int mid_val)
{
	int pos,i,j;
	int mid = (order+1)/2;
	bnode* t = c->parent;
	for(i=0;i<=order;i++)
	{
			if(t->index_ptr[i] == c)
				break;
	}
	pos =i;
	int *b=new int[order+1];
	sortarray1(t,mid_val,b);
	int mid_valb=*(b+mid);
	bnode* new1 = (bnode*)malloc(sizeof(bnode));
	init(new1);
	for(i=0;i<mid;i++)
	{
			new1->key[i]=*(b+i);
	}
	new1->fill_fact = i;
	bnode* new2 = (bnode*)malloc(sizeof(bnode));
	init(new2);
	for(i=mid+1,j=0;i<=order;i++,j++)
	{
			new2->key[j] = *(b+i);
	}
	new2->fill_fact=j;
	delete[] b;
	if(pos < mid)
	{
		for(i=0;i<=(new1->fill_fact);i++)
			{
				if(i==pos)
				{
					new1->index_ptr[i]=t1;
					t1->parent = new1;
				}
				else if( i == pos+1)
				{
					new1->index_ptr[i] = t2;
					t2->parent =new1;
				}
				else if(i>pos)
				{
					new1->index_ptr[i] = t->index_ptr[i-1];
					t->index_ptr[i-1]->parent = new1;
				}
				else
				{
					new1->index_ptr[i] = t->index_ptr[i];
					t->index_ptr[i]->parent = new1;
				}
			}
			for(i=0,j=mid;i<=(new2->fill_fact) && j<=order;i++,j++)
			{
				new2->index_ptr[i] = t->index_ptr[j];
				t->index_ptr[j]->parent = new2;
			}

		}
		else if(pos == mid)
		{
			for(i=0;i<mid;i++)
			{
				new1->index_ptr[i] = t->index_ptr[i];
				t->index_ptr[i]->parent = new1;
			}
			new1->index_ptr[i] = t1;
			t1->parent = new1;
			new2->index_ptr[0] = t2;
			t2->parent = new2;
			for(i=1,j=mid+1;i<=new2->fill_fact;i++,j++)
			{
				new2->index_ptr[i] = t->index_ptr[j];
				t->index_ptr[j]->parent = new2;
			}

		}
		else
		{
			for(i=0;i<=mid;i++)
			{
				new1->index_ptr[i] = t->index_ptr[i];
				t->index_ptr[i]->parent = new1;
			}
			for(i=new2->fill_fact;i>=0;i--)
			{
				if(i == new2->fill_fact)
					{
                        new2->index_ptr[i] = t2;
                        t2->parent = new2;
                        }
				else if(i == (new2->fill_fact -1))
					{
                          new2->index_ptr[i] = t1;
                          t1->parent = new2;
                          }
				else
					{
                          new2->index_ptr[i] = t->index_ptr[order-1];
                          t->index_ptr[order-1]->parent = new2;
                          }
			}

			
		}
		if(t->parent == NULL)
		{
			bnode* pp= (bnode*)malloc(sizeof(bnode*)) ;
		    init(pp);
			pp->key[0] =mid_valb;
			pp->fill_fact=1;
			pp->parent =NULL;
			pp->index_ptr[0] = new1;
			pp->index_ptr[1] = new2;
			new1->parent =  new2->parent = pp;
			root = pp;
			return pp;

		}
		else
		{
			if(t->parent->fill_fact < order)
			{
				bnode* r = par_space(new1,new2,t,mid_valb);
				return r;
			}
			else
			{
				bnode* r = par_full(new1,new2,t,mid_valb);
				return r;
			}

		}

}

bnode* btree::sortarray(bnode* cur,int key)
{
	int mid = (int)((order+1)/2);
	int *a = new int[order+1];
	sortarray1(cur,key,a);
	int mid_val = *(a + mid);
	int i,j;
	bnode* temp_node1 = (bnode*)malloc(sizeof(bnode));
	init(temp_node1);
	bnode* temp_node2 = (bnode*)malloc(sizeof(bnode));
	init(temp_node2);
	for(i=0;i<mid;i++)
	{
		temp_node1->key[i] = *(a+i);
	}
	temp_node1->fill_fact = i;
	for(i=mid,j=0;i<=order && j<order;i++,j++)
	{
			temp_node2->key[j] = *(a+i);
	}
	temp_node2->fill_fact = j;
	delete[] a;
	
	//propogation


	if(cur->parent == NULL)
	{
		bnode *res = par_nul(temp_node1,temp_node2,cur,mid_val);
		return res;
	}
	else if(cur->parent->fill_fact == order)
	{
		bnode* res = par_full(temp_node1,temp_node2,cur,mid_val);
		return res;
		
		
	}

	else
	{
		
		bnode* res=par_space(temp_node1,temp_node2,cur,mid_val);
		return res;
		
	}

}


int btree::insert(int key)
{
	bnode* target_node = search_leaf(root,key);
	
	if(target_node->fill_fact < order)
	{
			if(target_node->fill_fact == 0)
			{     
				target_node->key[0] = key;
				target_node->fill_fact++;
				return 0;
				
			}
			else 
			{
				
				sortedentry(target_node,key);
				return 0;
			}
	}
	else
	{
		//SORT THE KEY & NODE VALUES
		
		bnode *p = sortarray(target_node,key);
		return 0;
	}
	
}
/*------------------------------------------------------------------------*/
bnode* btree::search_node(bnode *t, int key)
{
	int i,f;
	bnode* res;
	f = t->fill_fact;
	for(i = 0 ; i<f  ; i++)
	{
		if(key == t->key[i])
		{
			return t;
		}
		if(i ==0 || i == f-1)
		{
			if(key < t->key[i])
			{
				res = search_node(t->index_ptr[i],key);
				return res;
			}
			if(key >t->key[i])
			{
				res = search_node(t->index_ptr[i+1],key);
				return res;
			}
		}
		else
		{
			if(key < t->key[i] && key > t->key[i-1])
			{
				res =search_node(t->index_ptr[i],key);
				return res;
			}
			else
			{
				if(key>t->key[i] && key<t->key[i-1])
				{
					res =search_node(t->index_ptr[i+1],key);
					return res;
				}
			}


		}
	}
	return NULL;
}
void btree::rytdistribute(bnode* target,bnode* sibling,int pos)
{
	int tf= target->fill_fact;
	target->key[tf] = sibling->key[0];
	target->fill_fact++;
	int i;
	for(i=0;i<sibling->fill_fact;i++)
	{
		sibling->key[i] = sibling->key[i+1];
	}
	sibling->fill_fact --;
	bnode* p = sibling->parent;
	p->key[pos] = sibling->key[0];

}
void btree::lftdistribute(bnode* target,bnode* sibling,int pos)
{
	int tf= target->fill_fact;
	int sf = sibling->fill_fact;
	bnode* p = target->parent;
	int i=0;
	for(i=tf;i>0;i--)
	{
		target->key[i] = target->key[i-1];
	}
	target->key[0] = sibling->key[sf-1];
	sibling->key[sf-1] = -1;
	sibling->fill_fact --;
	target->fill_fact++;
	p->key[pos-1] = target->key[0];
}
void btree::rytmerge(bnode* t,bnode* sibling,int pos)
{
                int i,j;
                int tf = t->fill_fact;
                int sf = sibling->fill_fact; 
                bnode* p = t->parent;
                for(i=tf,j=0;j<sf;j++,i++)
                {
                                          t->key[i] = sibling->key[j];
                }
                for(i=pos;i<p->fill_fact;i++)
                {
                     p->key[pos] = p->key[pos+1];
                                             
                }
                p->index_ptr[pos] = t;
               p->fill_fact--;
                for(i = pos+1;i<= p->fill_fact;i++)
                {
                      p->index_ptr[i] = p->index_ptr[i+1];
                }
                t->fill_fact = sf+1;
                
                                          
}
void btree::lftmerge(bnode* t,bnode* sibling,int pos)
{
     int tf = t->fill_fact;
     int sf = sibling->fill_fact;
     bnode* p = sibling->parent;
     int i,j;
     for(i= sf,j=0;j<tf;i++,j++)
     {
            sibling->key[i] = t->key[j];
     }
     sibling->fill_fact = tf+sf;
     p->key[pos-1] = -1;
     p->index_ptr[pos] = NULL;
     p->fill_fact -- ;
            
     
 }
int btree::delete_key(int key)
{
	bnode* t_leaf = search_leaf(root,key);
	int pos=0,i;
	for(i = 0;i<t_leaf->fill_fact ; i++)
	{
		if(t_leaf->key[i] == key)
		{
			pos = i;
			break;
		}
	}
	for( i =pos;i<t_leaf->fill_fact;i++)
	{
		t_leaf->key[i] = t_leaf->key[i+1];
	}
	t_leaf->fill_fact --;
	//bnode* i_entry = search_node(root,key);
	bnode* p = t_leaf->parent;
	if(t_leaf->fill_fact >= order/2)
	{
		return 0;
	}
	else
	{
		for(i = 0;i<=p->fill_fact ; i++)
		{
			if(p->index_ptr[i] == t_leaf)
					break;
		
		}
		pos=i;
		
		if(i == 0)
		{
			if(p->index_ptr[i+1]->fill_fact > order/2)
				rytdistribute(t_leaf,p->index_ptr[i+1],pos);
			else
				rytmerge(t_leaf,p->index_ptr[i+1],pos);
		}
		else if( i == p->fill_fact)
		{
			if(p->index_ptr[i-1]->fill_fact >order/2)
				lftdistribute(t_leaf,p->index_ptr[i-1],pos);
			else 
				lftmerge(t_leaf,p->index_ptr[i-1],pos);
		}
		else
		{
			if(p->index_ptr[i+1]->fill_fact  > order/2)
				rytdistribute(t_leaf,p->index_ptr[i+1],pos);
			else if(p->index_ptr[i-1]->fill_fact >order/2)
				lftdistribute(t_leaf,p->index_ptr[i-1],pos);
			else 
				rytmerge(t_leaf,p->index_ptr[i+1],pos);

		}
		return 0;
	}

	
}
static int level=0;
bnode* btree::show(bnode* temp)
{
	int i;
	
	for(i=0;i<temp->fill_fact;i++)
	{
		
		cout<<"\t"<<"key "<<i<<"-> : "<<temp->key[i]<<endl;
	}
	
	return temp;
	
}
void btree::showchild(bnode * temp)
{
	int i =0;
	bnode* b;
	if(temp->index_ptr[i] != NULL)
	{	level++;
	cout<<"LEVEL : "<<level<<endl;
	
	while(temp->index_ptr[i] != NULL && i<=order)
	{
		b =	show(temp->index_ptr[i]);
		i++;
		cout<<endl;
	}
	
	}
}

void btree::display()
 {	
	 level = 0;
	 cout<<"LEVEL : "<<level;
	 cout<<endl;
	 bnode* b = show(root);
	 
	 int i=0;
	 
	 showchild(b);
	 while(b->index_ptr[i] != NULL && i<(order+1))
	 {
		 bnode* t;
		 t = b->index_ptr[i];
		 cout<<endl;
		 showchild(t);
		 i++;
 	 }
	 
 }

 int main()
 {
	int x,j;
	btree b;
	b.initr();
	
	for(j=0;j<12;j++)
	{
	cout<<"enter  value"<<endl;
	cin>>x;
	int a = b.insert(x);
	b.display();
	}
	cout<<"deeelete 130"<<endl;
	b.delete_key(130);
	b.display();
	
	cout<<"deeelete 120";
	b.delete_key(120);
	b.display();

	getch();
	return 0;
 }


